
package nsga;

/**
 *
 * @author Gustavo Planás
 */

import java.util.ArrayList;

public class NSGA 
{
    
    // Constantes
    private int MAX_GEN = 100; // Cantidad máxima de Generaciones
    private int CANT_IND = 100; // Cantidad de Individuos de cada Población
    private double EPSILON = 0.1; // Valor de Degradación de los Frentes
    private double SIGMA = 0.01; // Distancia Mínima para realizar Sharing
    private double PROB_MUT = 0.1; // Probabilidad de Mutación de un Individuo
    private double SIGMA_FRENTE = 100; // Distancia Mínima para que un punto sea considerado en la Métrica Distribución de Frentes
    
    // Variables del Algoritmo
    private Individuo[] poblacion = new Individuo[CANT_IND]; // Vector de Individuos que representa la Población
    private int[] poblacion_frentes = new int[CANT_IND]; // Vector de Frentes de los Individuos de la Población
    private Individuo[] nueva_gen = new Individuo[CANT_IND]; // Vector de Individuos de la Nueva Población
    private int[] frente_actual = new int[CANT_IND]; // Contiene las posiciones del Vector de Población de los Individuos del Frente Actual
    private double[] sharing_frente_actual = new double[CANT_IND]; // Contiene los valores de Sharing para el Frente Actual
    ArrayList<Individuo> conjuntoPareto = new ArrayList<Individuo>(); // Frente Pareto
    
    private int frente; // Contador de Frentes
    boolean clasificada; // Marca la Población como Clasificada
    private double dummy_fitness; // Valor del Dummy Fitness
    private int cant_frente_actual; // Cantidad de Individuos del Frente Acutal
    
    // Cambiar para otras pruebas.
    private static String archivo = "C:\\Datos60.txt";
    
    public static void main(String[] args)throws Exception
    {
        ArrayList<Individuo> conjuntoParetoGlobal=new ArrayList<Individuo>();
        System.out.println("SCICTD");
        NSGA nsga;
        //for(int i=0;i<3;i++)
        //{
            //System.out.println("Corrida:"+i);
            nsga = new NSGA(SCICTD.main(archivo));
            //nsga = new NSGA(SCICTD.main(args[0]));
            conjuntoParetoGlobal.addAll(nsga.conjuntoPareto);
        //}
        int j=0;
        while(j<conjuntoParetoGlobal.size())
            {
                double[] fitnessIndividuoConjuntoPareto=conjuntoParetoGlobal.get(j).getFitness();
                for(int k=0;k<conjuntoParetoGlobal.size();k++)
                {
                    double[] fitnessIndividuoPoblacion=conjuntoParetoGlobal.get(k).getFitness();
                    if((fitnessIndividuoConjuntoPareto[0]==fitnessIndividuoPoblacion[0])&&(fitnessIndividuoConjuntoPareto[1]>fitnessIndividuoPoblacion[1]))
                    {
                        conjuntoParetoGlobal.remove(j);
                        j--;
                        break;
                    }
                    else if((fitnessIndividuoConjuntoPareto[1]==fitnessIndividuoPoblacion[1])&&(fitnessIndividuoConjuntoPareto[0]>fitnessIndividuoPoblacion[0]))
                    {
                        conjuntoParetoGlobal.remove(j);
                        j--;
                        break;
                    }
                    else if((fitnessIndividuoConjuntoPareto[0]>fitnessIndividuoPoblacion[0])&&(fitnessIndividuoConjuntoPareto[1]>fitnessIndividuoPoblacion[1]))
                    {
                        conjuntoParetoGlobal.remove(j);
                        j--;
                        break;
                    }
                }
                j++;
            }
        System.out.println("");
        System.out.println("Y true");
        double[] fitness;
        int[] solucion;
        for(int i=0;i<conjuntoParetoGlobal.size();i++)
        {
            System.out.println("Individuo:"+i);
            fitness=conjuntoParetoGlobal.get(i).getFitness();
            System.out.println("Objetivo 1:"+fitness[0]);
            System.out.println("Objetivo 2:"+fitness[1]);
            //if(conjuntoParetoGlobal.get(i) instanceof IndividuoTSP)
            //{
                solucion=((IndividuoSCICTD)conjuntoParetoGlobal.get(i)).getNodos();
                for(j=0;j<solucion.length;j++)
                    System.out.print(solucion[j]);
            //}
            //else if(conjuntoParetoGlobal.get(i) instanceof IndividuoQAP)
            //{
                //solucion=((IndividuoQAP)conjuntoParetoGlobal.get(i)).getLocalidades();
                //for(j=0;j<solucion.length;j++)
                //{
                    //System.out.print(solucion[j]+"\t");
                //}
            //}
            //else if(conjuntoParetoGlobal.get(i) instanceof IndividuoVRPTW)
            //{
                //CamionVRPTW[] camiones=((IndividuoVRPTW)conjuntoParetoGlobal.get(i)).getCamiones();
                //for(j=0;j<camiones.length;j++)
                //{
                    //System.out.println("Camion:"+j);
                    //solucion=camiones[j].getOrden();
                    //for(int k=0;k<solucion.length;k++)
                    //{
                        //System.out.print(solucion[k]+"\t");
                    //}
                    //System.out.println("0");
                //}
            //}
            System.out.println();
        }
    }
    
    private NSGA(Problema problema) 
    {
        // Inicializa la Población
        inicializarPoblacion(problema);
        // Ciclo de Generaciones
        for(int gen = 0; gen < MAX_GEN; gen++) 
        {
            calcularFitnessPoblacion(problema); // Calcula el Fitness de todos los Individuos de la Población
            inicializarFrentes(); // Inicializa Frentes con el Valor 0
            frente = 0; // Inicializa Contador de Frentes
            clasificada = false;
            dummy_fitness = CANT_IND; // Inicializa el Dummy Fitness al Tamaño de la Población
            // Mientrás existan individuos sin Clasificar
            while(!clasificada) 
            {
                frente++; // Aumenta el Contador de Frentes
                cant_frente_actual = 0; // Setea la cantidad de Individuos del Frente Actual a 0
                // Identificar Individuos no dominados (Si no hay, clasificado = true)
                for(int i = 0; i < CANT_IND; i++) 
                {
                    if (poblacion_frentes[i] == 0) 
                    {
                        boolean dominado = false;
                        for(int j = 0; j < CANT_IND; j++) 
                        {
                            if (poblacion_frentes[j] == 0) 
                            {
                                dominado = verificarDominancia(poblacion[i], poblacion[j]);
                                if(dominado)
                                    break;
                            }
                        }
                        if(!dominado) 
                        {
                            poblacion_frentes[i] = frente; // Asigna el Frente Actual al Individuo i
                            poblacion[i].setFitnessAlgoritmo(dummy_fitness); // Asigna el Dummy Fitness
                            frente_actual[cant_frente_actual] = i; // Carga el Vector Frente Actual
                            cant_frente_actual++; // Aumenta la Cantidad de Individuos del Frente
                        }
                    }
                }
                fitnessSharing(); // Realiza el Fitness Sharing
                dummy_fitness = calcularMinimoValorDeFitnessDelFrenteActual(); // Guarda el Peor Valor del Dummy Fitness
                dummy_fitness = dummy_fitness - EPSILON; // Reduce el Peor Valor en EPSILON para usarlo para el siguiente Frente
                clasificada = verificarPoblacionClasificada(); // Verifica si existen Individuos sin clasificar en la Población
            }
            // Actualiza el Conjunto Pareto
            actualizarConjuntoPareto();
            // Selección por Ruleta
            int cant_nueva_gen = 0; // Cantidad de Individuos de la Nueva Generación
            for(int i = 0; i < CANT_IND / 2; i++) 
            {
                Individuo ind1 = seleccionRuleta(); // Selecciona un Individuo por el Método de la Ruleta
                Individuo ind2 = seleccionRuleta(); // Selecciona un Individuo por el Método de la Ruleta
                // Cruzamiento
                Individuo[] nuevos_inds = problema.cruzar(ind1, ind2);
                // Nueva Generación
                nueva_gen[cant_nueva_gen] = nuevos_inds[0]; // Agrega el primer Hijo a la Nueva Generación
                cant_nueva_gen++;
                nueva_gen[cant_nueva_gen] = nuevos_inds[1]; // Agrega el segundo Hijo a la Nueva Generación
                cant_nueva_gen++;
            }
            // Mutación
            for(int i = 0; i < CANT_IND; i++) 
            {
                if(Math.random() < PROB_MUT)
                    nueva_gen[i].mutar();
            }
            // Actualiza la Población
            actualizarPoblacion();
            //System.out.println("Generación " + gen);
        }
        imprimirResultados();
        metricasDeComparacion();
    }
    
    private void inicializarPoblacion(Problema problema) 
    {
        // Inicializa la Población
        for(int i = 0; i < CANT_IND; i++) 
        {
            Individuo individuo = null;
            if(problema.getTipo() == 0)
            {
                individuo = IndividuoTSP.getIndividuoGeneradoAleatoriamente(problema.getLength());
            }
            else if(problema.getTipo() == 1)
            {
                individuo = IndividuoQAP.getIndividuoGeneradoAleatoriamente(problema.getLength());
            }
            else if(problema.getTipo() == 2)
            {
                VRPTW vrptw = (VRPTW) problema;
                individuo = IndividuoVRPTW.getIndividuoGeneradoAleatoriamente(vrptw.getClientes(), vrptw.getTiempos(), vrptw.getCapacity());
            }
            else if(problema.getTipo() == 3)
            {
                SCICTD scictd = (SCICTD) problema;
                individuo = IndividuoSCICTD.getIndividuoAleatorio(problema.getLength());
            }
            poblacion[i] = individuo;
        }
    }
    
    private void inicializarFrentes() 
    {
        // Inicializa Frentes con el Valor 0
        for(int i = 0; i < CANT_IND; i++) 
        {
            poblacion_frentes[i] = 0; // El valor cero indica que aún no se ha Clasificado el Individuo
        }
    }
    
    private void calcularFitnessPoblacion(Problema problema) 
    {
        // Calcula el Fitness de todos los Individuos de la Población
        for(int i = 0; i < CANT_IND; i++) 
        {
            problema.setFitness(poblacion[i]);
        }
    }
    
    private boolean verificarDominancia(Individuo indi, Individuo indj) 
    {
        // Devuelve True si el Individuo j domina al Individuo i. False en caso contrario
        double[] fii = indi.getFitness(); // Fitness del Individuo i
        double[] fij = indj.getFitness(); // Fitness del Individuo j
        if(fij[0] < fii[0] && fij[1] < fii[1])
            return true;
        if(fij[0] == fii[0] && fij[1] < fii[1])
            return true;
        if(fij[0] < fii[0] && fij[1] == fii[1])
            return true;
        return false;
    }
    
    private void fitnessSharing() 
    {
        double sharing;
        // Inicaliza el Sharing del Frente Actual
        for(int i = 0; i < cant_frente_actual; i++)
            sharing_frente_actual[i] = 0;
        // Calcula el Fitness Sharing
        for(int i = 0; i < cant_frente_actual; i++) 
        {
            for(int j = 0; j < cant_frente_actual; j++) 
            {
                double distancia = distanciaEuclidea(poblacion[frente_actual[i]], poblacion[frente_actual[j]]); // Calcula la Distancia Euclídea entre los puntos de 2 Individuos
                if (distancia <= SIGMA)
                    sharing = 1 - Math.pow(distancia / SIGMA, 2);
                else
                    sharing = 0;
                sharing_frente_actual[i] = sharing_frente_actual[i] + sharing;
            }
            poblacion[frente_actual[i]].setFitnessAlgoritmo(poblacion[frente_actual[i]].getFitnessAlgoritmo() / sharing_frente_actual[i]);
        }
    }
    
    private double distanciaEuclidea(Individuo indi, Individuo indj) 
    {
        // Calcula la Distancia Euclídea entre los puntos de 2 Individuos
        double[] fii = indi.getFitness(); // Fitness del Individuo i
        double[] fij = indj.getFitness(); // Fitness del Individuo j
        return Math.sqrt(Math.pow(fii[0] - fij[0], 2) + Math.pow(fii[1] - fij[1], 2));
    }
    
    private double calcularMinimoValorDeFitnessDelFrenteActual() 
    {
        // Calcula y devuelve el Mínimo Valor de Fitness del Frente Actual
        double min = poblacion[frente_actual[0]].getFitnessAlgoritmo();
        for(int i = 1; i < cant_frente_actual; i++) 
        {
            if (poblacion[frente_actual[i]].getFitnessAlgoritmo() < min)
                min = poblacion[frente_actual[i]].getFitnessAlgoritmo();
        }
        return min;
    }
    
    private boolean verificarPoblacionClasificada() 
    {
        // Verifica si existen Individuos sin clasificar en la Población
        for(int i = 0; i < CANT_IND; i++) 
        {
            if (poblacion_frentes[i] == 0)
                return false;
        }
        return true;
    }

    private void actualizarPoblacion() {
        // Copia la Nueva Generación a la Población Actual
        for(int i = 0; i < CANT_IND; i++) {
            poblacion[i] = nueva_gen[i]; //.clone();
        }
    }
    
    private void actualizarConjuntoPareto() {
        // Actualiza el Conjunto Pareto
        // Primero: Eliminar los Elementos del Conjunto Pareto que son dominados por el Primer Frente
        int cant_pareto = conjuntoPareto.size();
        int i = 0;
        while(i < cant_pareto) {
            for(int j = 0; j < CANT_IND; j++) {
                if (poblacion_frentes[j] == 1) {
                    if(verificarDominancia(conjuntoPareto.get(i), poblacion[j])) {
                        conjuntoPareto.remove(i);
                        i--;
                        cant_pareto--;
                        break;
                    }
                }
            }
            i++;
        }
        // Segundo: Agregar al Conjunto Pareto los Individuos del Primer Frente si nadie del Conjunto Pareto domina a ese Individuo
        for(int j = 0; j < CANT_IND; j++) {
            if (poblacion_frentes[j] == 1) {
                int k = 0;
                boolean dominado = false;
                while(k < cant_pareto) {
                    if(verificarDominancia(poblacion[j], conjuntoPareto.get(k))) {
                        dominado = true;
                        break;
                    }
                    k++;
                }
                if(!dominado) {
                    conjuntoPareto.add(poblacion[j].clone());
                    cant_pareto++;
                }
            }
        }
    }
    
    private Individuo seleccionRuleta() {
        // Devuelve un Individuo seleccionado por el Método de la Ruleta
        double sum = 0;
        for(int i = 0; i < CANT_IND; i++) {
            sum = sum + poblacion[i].getFitnessAlgoritmo();
        }
        double r;
        do {
            r = Math.random() * Math.pow(10, String.valueOf((int) sum).length());
        } while(r >= sum);
        for(int i = 0; i < CANT_IND; i++) {
            r = r - poblacion[i].getFitnessAlgoritmo();
            if (r <= 0)
                return poblacion[i];
        }
        return null; // Si no se seleccionó ningún Individuo
    }
    
    private void imprimirResultados() {
        // Imprime los Resultados de la corrida de un Algoritmo
        System.out.println();
        double[] fitness;
        int[] solucion;
        int actual;
        for(int i = 0; i < conjuntoPareto.size(); i++)
        {
            System.out.println("Individuo: " + i);
            fitness = conjuntoPareto.get(i).getFitness();
            System.out.println("Objetivo 1: " + fitness[0]);
            System.out.println("Objetivo 2: " + fitness[1]);
            //if(conjuntoPareto.get(i) instanceof IndividuoTSP)
            //{
                solucion = ((IndividuoSCICTD) conjuntoPareto.get(i)).getNodos();
                for(int j = 0; j < solucion.length; j++)
                    System.out.print(solucion[j]);
            //}
            //else if(conjuntoPareto.get(i) instanceof IndividuoQAP)
            //{
                //solucion=((IndividuoQAP)conjuntoPareto.get(i)).getLocalidades();
                //for(int j=0;j<solucion.length;j++)
                //{
                    //System.out.print(solucion[j]+"\t");
                //}
            //}
            //else if(conjuntoPareto.get(i) instanceof IndividuoVRPTW)
            //{
                //CamionVRPTW[] camiones=((IndividuoVRPTW)conjuntoPareto.get(i)).getCamiones();
                //for(int j=0;j<camiones.length;j++)
                //{
                    //System.out.println("Camion:"+j);
                    //solucion=camiones[j].getOrden();
                    //for(int k=0;k<solucion.length;k++)
                    //{
                        //System.out.print(solucion[k]+"\t");
                    //}
                    //System.out.println("0");
                //}
            //}
            System.out.println();
        }
    }
    
    private void metricasDeComparacion() {
        // Calcula las Métricas de Comparación de Frentes
        // 1) Distancia al Frente Y true
        
        // 2) Distribución del Frente Y'
        int cantidad = 0;
        for(int i = 0; i < conjuntoPareto.size(); i++)
        {
            for(int j = 0; j < conjuntoPareto.size(); j++)
            {
                if(distanciaEuclidea(conjuntoPareto.get(i), conjuntoPareto.get(j)) > SIGMA_FRENTE)
                    cantidad++;
            }
        }
        double distribucion = 0;
        if(conjuntoPareto.size() > 1)
            distribucion = cantidad / (conjuntoPareto.size() - 1);
        System.out.println("Distribución del Frente Y' " + distribucion);
        
        // 3) Extensión del Frente Y'
        double extension = 0;
        for(int i = 0; i < conjuntoPareto.size(); i++)
        {
            for(int j = 0; j < conjuntoPareto.size(); j++)
            {
                if(distanciaEuclidea(conjuntoPareto.get(i), conjuntoPareto.get(j)) > extension)
                    extension = distanciaEuclidea(conjuntoPareto.get(i), conjuntoPareto.get(j));
            }
        }
        System.out.println("Extensión del Frente Y' " + extension);
    }
}
